package com.zhangxiaofanfan.hotcode.fourth.third;


/**
 * TODO
 *
 * @author zhangxiaofanfan
 * @date 2024-06-26 20:33:33
 */
public class HotCode060 {
    public static void main(String[] args) {
        HotCode060 hotCode060 = new HotCode060();
        char[][] board = {
            {'A','B','C','E'},
            {'S','F','C','S'},
            {'A','D','E','E'}
        };
        String word = "ABCCED";
        HotCode060 hotCod = new HotCode060();
        System.out.println(hotCod.exist(board, word));
    }

    private final int[][] dires = new int[][] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public boolean exist(char[][] board, String word) {
        int row = board.length, col = board[0].length;
        char[] words = word.toCharArray();
        for (int rowIndex = 0, colIndex; rowIndex < row; rowIndex++) {
            for (colIndex = 0; colIndex < col; colIndex++) {
                if (exist(rowIndex, colIndex, board, words, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean exist(int rowIndex, int colIndex, char[][] board, char[] word, int wordIndex) {
        if (wordIndex >= word.length) {
            return true;
        }
        if (rowIndex < 0 || rowIndex >= board.length || colIndex < 0 || colIndex >= board[0].length || board[rowIndex][colIndex] != word[wordIndex]) {
            return false;
        }
        board[rowIndex][colIndex] = 0;
        for (int[] dire : dires) {
            if (exist(rowIndex + dire[0], colIndex + dire[1], board, word, wordIndex + 1)) {
                return true;
            }
        }
        board[rowIndex][colIndex] = word[wordIndex];
        return false;
    }

}
